#pragma once

#include <string>
#include <vector>

namespace solution_224
{

class Solution
{
public:
    struct Node {
        int val = 0;
        char op = 0;
        explicit Node(int val) : val(val) {}
        explicit Node(char op) : op(op) {}
    };

    int calculate(std::string s)
    {
        std::vector<Node> nodes;
        for (auto ch : s) {
            if (ch >= '0' && ch <= '9') {
                if (nodes.empty() || nodes.back().op)
                    nodes.emplace_back(0);
                nodes.back().val *= 10;
                nodes.back().val += ch - '0';
            } else if (ch == '(' || ch == ')') {
                nodes.emplace_back(ch);
            } else if (ch == '+' || ch == '-') {
                if (nodes.empty() || nodes.back().op == '(')
                    nodes.emplace_back(0);
                nodes.emplace_back(ch);
            }
        }

        std::vector<Node> stack;
        for (auto& node : nodes) {
            stack.push_back(node);
            if (!stack.empty() && stack.back().op == ')') {
                stack.pop_back();
                stack.at(stack.size() - 2) = stack.back();
                stack.pop_back();
            }
            while (stack.size() >= 3) {
                int s = stack.size();
                if ( stack.at(s - 3).op == 0 &&
                     stack.at(s - 1).op == 0 &&
                     (stack.at(s - 2).op == '+' || stack.at(s - 2).op == '-') ) {
                    auto a = stack.at(s - 3).val;
                    auto op = stack.at(s - 2).op;
                    auto b = stack.at(s - 1).val;

                    stack.at(s - 3).val = (op == '+') ? a + b : a - b;
                    stack.pop_back();
                    stack.pop_back();
                } else {
                    break;
                }
            }
        }
        return stack.back().val;
    }
};

}  /* namespace solution_224 */
